Partial MaxSAT (PMS) and Weighted PMS (WPMS) are two practical generalizations of the MaxSAT problem. In this paper, we propose a local search algorithm for these problems, called BandHS, which applies two multi-armed bandits to guide the search directions when escaping local optima. One bandit is combined with all the soft clauses to help the algorithm select to satisfy appropriate soft clauses, and the other bandit with all the literals in hard clauses to help the algorithm select appropriate literals to satisfy the hard clauses. These two bandits can improve the algorithm's search ability in both feasible and infeasible solution spaces. We further propose an initialization method for (W)PMS that prioritizes both unit and binary clauses when producing the initial solutions. Extensive experiments demonstrate the excellent performance and generalization capability of our proposed methods, that greatly boost the state-of-the-art local search algorithm, SATLike3.0, and the state-of-the-art SAT-based incomplete solver, NuWLS-c.

我们解决了部分MaxSat（PMS）和加权PMS（WPM），这是MaxSat问题的两个实际概括，并为这些问题（称为BandMaxSat）提出了一种局部搜索算法，该算法应用了多臂Bantit模型来指导搜索方向。我们方法中的匪徒与输入（w）pms实例中的所有软子句相关联。每个手臂对应于软子句。 Bandit模型可以通过选择要在当前步骤中满足的软子句，即选择要拉的臂来帮助BandmaxSat选择一个良好的方向以逃脱本地Optima。我们进一步提出了一种初始化方法（w）PMS，在生产初始解决方案时优先考虑单元和二进制条款。广泛的实验表明，BandMaxSat显着优于最先进的（W）PMS本地搜索算法SATLIKE3.0。具体而言，BandMaxSat获得更好结果的实例数量大约是Satlike3.0获得的两倍。此外，我们将bandmaxsat与完整的求解器tt-open-wbo-inc相结合。最终的求解器bandmaxsat-c还胜过一些最好的最新完整（W）PMS求解器，包括satlike-c，loandra和tt-open-wbo-inc。